class Solution:
    def solveNQueens(self, n):
        """解决N皇后问题

        Args:
            n: 棋盘大小

        Returns:
            所有可行解的棋盘布局列表
        """

        def backtrack(row, cols, diag1, diag2, path):
            if row == n:
                solutions.append(path[:])  # 使用切片复制列表
                return

            for col in range(n):
                curr_diag1 = row - col
                curr_diag2 = row + col

                if col in cols or curr_diag1 in diag1 or curr_diag2 in diag2:
                    continue

                cols.add(col)
                diag1.add(curr_diag1)
                diag2.add(curr_diag2)
                path.append('.' * col + 'Q' + '.' * (n - col - 1))

                backtrack(row + 1, cols, diag1, diag2, path)

                cols.remove(col)
                diag1.remove(curr_diag1)
                diag2.remove(curr_diag2)
                path.pop()

        solutions = []
        backtrack(0, set(), set(), set(), [])
        return solutions


# 示例输出格式
if __name__ == "__main__":
    sol = Solution()
    n = 4
    result = sol.solveNQueens(n)
    print(f"n={n}的解:")
    print(result)